package 力扣.动态规划;

import java.util.Arrays;

public class 最大子序和53 {

    public static void main(String[] args) {
        int[] ints = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
//        int[] ints = {-2, 1, -3, 9,100,1,-9,1000,-10,11,-12,13};
//        int[] ints = {-2,-1,1,9,-100};
//        int[] ints = {-2,-1,-1};
//        int[] ints = {1,2,-1,-2,2,1,-2,1,4,-5,4};
        int i = maxSubArray(ints);
        System.out.println(i);
    }


    /**
     * 落差法+前缀和
     * 前缀和：开辟一个数组C[N]，其中C[i] ==（B[0]+B[1]+B[2]+....+B[i]）
     * 利用前缀和计算最大落差;当前前缀和C[i] ‘减去’ 之前的最小前缀和B[j] 得到的结果就是‘最大落差’ 即B[j+1] ~ B[i] 这个连续的子数组的总和
     * 而此时仅仅是[j+1,i]之间的最大和，还要判断B[i]是否为正数，来决定B[i]是否加入，最终决定真正的最大和。这里巧用初始化pre_MIN = 0作为一个最小前缀和来使用
     *
     * 真正做题的时候，其实不需要开辟一个C[]数组，前缀和在数组遍历过程中只需要两个整数来代替即可：pre:当前前缀和C[i],pre_MIN:当前最小前缀和
     * pre - pre_MIN表示当前最大落差
     * @param nums
     * @return
     */
    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int N = nums.length;
       int pre = 0;//pre表示C[i]的值
       int pre_MIN = 0;//巧用初始化0，作为一个初始前缀和
       int ans = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            int te = nums[i];
            pre += te;//当前前缀和
            ans = Math.max(ans, pre - pre_MIN);//得到当前最大落差和之前的最大落差ans 进行比较
            pre_MIN = Math.min(pre, pre_MIN);//得到当前最小前缀和
        }
        return ans;
    }












    public int maxSubArray2(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int pre = 0;
        int pre_MIN = 0;
        int ans = Integer.MIN_VALUE;
        for (int te: nums) {
            pre += te;
            ans = Math.max(ans, pre - pre_MIN);
            pre_MIN = Math.min(pre_MIN, pre);
        }
        return  ans;
    }
}
